---
title: STL Containers
---

The C++ Standard Template Library (STL) provides a rich set of generic classes and functions that implement common data structures and algorithms. **Containers** are objects that store data. They are template classes, meaning they can hold elements of any data type. Understanding STL containers is crucial for efficient and robust C++ programming, offering a powerful alternative to JavaScript's built-in array and object types.

## Sequence Containers: `vector`, `list`, `deque`

Sequence containers store elements in a linear fashion, allowing access to elements by their position.

### `std::vector`

*   **Dynamic Array:** Similar to JavaScript arrays, `std::vector` is a dynamic array that can grow or shrink in size.
*   **Contiguous Memory:** Elements are stored in contiguous memory locations, allowing for efficient random access (O(1)).
*   **Efficient Back Insertion/Deletion:** Adding/removing elements at the end is efficient (amortized O(1)).
*   **Inefficient Middle Insertion/Deletion:** Inserting/deleting in the middle requires shifting elements (O(n)).

<UniversalEditor title="Vector vs. JavaScript Array" compare={true}>
```javascript !! js
// JavaScript: Array
let numbers = [1, 2, 3];
numbers.push(4); // Add to end
console.log(numbers); // [1, 2, 3, 4]
console.log(numbers[1]); // 2 (random access)
numbers.splice(1, 0, 99); // Insert in middle
console.log(numbers); // [1, 99, 2, 3, 4]
```

```cpp !! cpp
// C++: std::vector
#include <iostream>
#include <vector>

int main() {
  std::vector<int> numbers = {1, 2, 3};
  numbers.push_back(4); // Add to end
  // std::cout << "Vector: ";
  // for (int n : numbers) { std::cout << n << " "; }
  // std::cout << std::endl;

  // std::cout << "Element at index 1: " << numbers[1] << std::endl; // 2 (random access)

  numbers.insert(numbers.begin() + 1, 99); // Insert in middle
  // std::cout << "Vector after insert: ";
  // for (int n : numbers) { std::cout << n << " "; }
  // std::cout << std::endl;

  return 0;
}
```
</UniversalEditor>

### `std::list`

*   **Doubly Linked List:** Elements are not stored contiguously. Each element stores pointers to the previous and next elements.
*   **Efficient Insertion/Deletion Anywhere:** Adding/removing elements anywhere in the list is efficient (O(1)) once the position is found.
*   **Inefficient Random Access:** Accessing elements by index requires traversing the list (O(n)).

### `std::deque` (Double-Ended Queue)

*   **Dynamic Array of Blocks:** Stores elements in non-contiguous blocks of memory.
*   **Efficient Front/Back Insertion/Deletion:** Adding/removing elements at both ends is efficient (amortized O(1)).
*   **Efficient Random Access:** Supports random access (O(1)), though slightly slower than `std::vector`.

## Associative Containers: `map`, `set`, `unordered_map`

Associative containers store elements in a sorted or hashed manner, allowing efficient lookup based on keys.

### `std::map`

*   **Sorted Key-Value Pairs:** Stores elements as key-value pairs, sorted by key.
*   **Unique Keys:** Each key must be unique.
*   **Logarithmic Time Complexity:** Lookup, insertion, and deletion operations are typically O(log n) due to its underlying tree structure (usually a Red-Black Tree).

<UniversalEditor title="Map vs. JavaScript Object" compare={true}>
```javascript !! js
// JavaScript: Object (used as a hash map)
let userAges = {
  "Alice": 30,
  "Bob": 25
};
userAges["Charlie"] = 35; // Add/Update
console.log(userAges["Alice"]); // Access
console.log("Bob" in userAges); // Check existence
delete userAges["Bob"]; // Delete
```

```cpp !! cpp
// C++: std::map
#include <iostream>
#include <map>
#include <string>

int main() {
  std::map<std::string, int> userAges;
  userAges["Alice"] = 30;
  userAges["Bob"] = 25;
  userAges["Charlie"] = 35; // Add/Update

  // std::cout << "Alice's age: " << userAges["Alice"] << std::endl; // Access

  // Check existence
  // if (userAges.count("Bob")) {
  //   std::cout << "Bob exists." << std::endl;
  // }

  userAges.erase("Bob"); // Delete

  return 0;
}
```
</UniversalEditor>

### `std::set`

*   **Sorted Unique Elements:** Stores unique elements in a sorted order.
*   **Logarithmic Time Complexity:** Lookup, insertion, and deletion are O(log n).

### `std::unordered_map`

*   **Hashed Key-Value Pairs:** Stores elements as key-value pairs using a hash table.
*   **Unique Keys:** Each key must be unique.
*   **Average Constant Time Complexity:** Lookup, insertion, and deletion are typically O(1) on average, but can degrade to O(n) in worst-case scenarios (hash collisions).

### `std::unordered_set`

*   **Hashed Unique Elements:** Stores unique elements using a hash table.
*   **Average Constant Time Complexity:** Lookup, insertion, and deletion are typically O(1) on average.

## Container Adapters: `stack`, `queue`, `priority_queue`

Container adapters provide a restricted interface to an underlying container, enforcing specific data access patterns.

### `std::stack`

*   **LIFO (Last-In, First-Out):** Elements are added and removed from the top.
*   **Operations:** `push`, `pop`, `top`, `empty`, `size`.

### `std::queue`

*   **FIFO (First-In, First-Out):** Elements are added to the back and removed from the front.
*   **Operations:** `push`, `pop`, `front`, `back`, `empty`, `size`.

### `std::priority_queue`

*   **Highest Priority First:** Elements are retrieved based on their priority (largest element by default).
*   **Operations:** `push`, `pop`, `top`, `empty`, `size`.

## Iterator Concept and Usage

**Iterators** are objects that act like pointers, allowing you to traverse through the elements of a container. They provide a generic way to access elements regardless of the container type.

*   `begin()`: Returns an iterator to the first element.
*   `end()`: Returns an iterator to the element *past* the last element (a sentinel).
*   `*iterator`: Dereferences the iterator to get the element's value.
*   `++iterator`: Moves the iterator to the next element.

<UniversalEditor title="Iterator Usage Comparison" compare={true}>
```javascript !! js
// JavaScript: Iteration using for...of or forEach
let fruits = ["apple", "banana", "cherry"];
for (let fruit of fruits) {
  console.log(fruit);
}

fruits.forEach(fruit => console.log(fruit));
```

```cpp !! cpp
// C++: Iterators
#include <iostream>
#include <vector>
#include <string>

int main() {
  std::vector<std::string> fruits = {"apple", "banana", "cherry"};

  // Using iterators with a traditional for loop
  // for (std::vector<std::string>::iterator it = fruits.begin(); it != fruits.end(); ++it) {
  //   std::cout << *it << std::endl;
  // }

  // Using range-based for loop (C++11+), which uses iterators internally
  // for (const std::string& fruit : fruits) {
  //   std::cout << fruit << std::endl;
  // }

  return 0;
}
```
</UniversalEditor>

## Container Performance Characteristics Analysis

Choosing the right container is crucial for performance. Here's a summary of typical time complexities for common operations:

| Container         | Access (Random) | Insertion (Anywhere) | Deletion (Anywhere) | Search (by value) |
| :---------------- | :-------------- | :------------------- | :------------------ | :---------------- |
| `std::vector`     | O(1)            | O(n)                 | O(n)                | O(n)              |
| `std::list`       | O(n)            | O(1)                 | O(1)                | O(n)              |
| `std::deque`      | O(1)            | O(n) (middle), O(1) (ends) | O(n) (middle), O(1) (ends) | O(n)              |
| `std::map`        | N/A             | O(log n)             | O(log n)            | O(log n)          |
| `std::set`        | N/A             | O(log n)             | O(log n)            | O(log n)          |
| `std::unordered_map` | N/A             | O(1) (avg), O(n) (worst) | O(1) (avg), O(n) (worst) | O(1) (avg), O(n) (worst) |
| `std::unordered_set` | N/A             | O(1) (avg), O(n) (worst) | O(1) (avg), O(n) (worst) | O(1) (avg), O(n) (worst) |

## Comparison with JavaScript Arrays/Objects

JavaScript's `Array` and `Object` types are highly versatile but abstract away the underlying memory management and specific data structures. C++ STL containers provide explicit choices, allowing developers to select the most performant data structure for their specific needs.

*   **JavaScript `Array`:** Behaves somewhat like a `std::vector` for numerical indices, but can also act as a hash map for string keys. It's a single, flexible data structure.
*   **JavaScript `Object`:** Primarily a hash map (key-value store), similar to `std::unordered_map` or `std::map` in functionality, but without the explicit performance guarantees or type safety of C++ containers.

## Container Selection Guide

*   **`std::vector`:** Your default choice for sequences. Use when you need fast random access and efficient additions/deletions at the end. Avoid frequent insertions/deletions in the middle.
*   **`std::list`:** Use when you need frequent insertions/deletions anywhere in the sequence and random access is not a primary concern.
*   **`std::deque`:** Use when you need efficient insertions/deletions at both ends and also require fast random access.
*   **`std::map` / `std::set`:** Use when you need sorted key-value pairs (map) or unique sorted elements (set) and logarithmic time complexity for operations. Useful when order matters.
*   **`std::unordered_map` / `std::unordered_set`:** Use when you need fast average-case O(1) lookup, insertion, and deletion, and the order of elements does not matter. Ideal for hash table-like behavior.
*   **`std::stack` / `std::queue` / `std::priority_queue`:** Use when you need specific LIFO, FIFO, or priority-based access patterns, respectively.

---

### Practice Questions:
1.  Describe the main differences between `std::vector` and `std::list` in terms of their underlying data structures and performance characteristics for insertion/deletion and random access.
2.  When would you choose `std::map` over `std::unordered_map`, and vice versa? Explain the trade-offs.
3.  How do iterators simplify working with different STL containers in C++? Provide a simple example of iterating through a `std::vector` and a `std::list` using iterators.

### Project Idea:
*   Implement a simple contact management system using `std::map` where the key is the contact's name (string) and the value is a struct/class containing their phone number and email. Allow users to add, delete, search, and display contacts. Then, try to implement the same system using `std::vector` of structs and compare the complexity of search operations.
